import java.util.Map;
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main1(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int n = in.nextInt();
            //先判断a是否为质数
            if(isPrimer(n)) {
                System.out.println(n + " = " + n);
                continue;
            }
            System.out.print(n + " = " );
            int len = n / 2;
            for(int i = 2; i <= len; i++){
                while(n % i == 0){
                    System.out.print(i);
                    n /= i;
                    if(n / i != 0) System.out.print(" * ");

                }

            }
            System.out.println();
        }
    }
    public static boolean isPrimer(int n){
        for(int i = 2; i <= Math.sqrt(n); i++){
            if(n % i == 0) return false;
        }
        return true;
    }
    //最长递增子序列
    public int lengthOfLIS(int[] nums) {
        //创建dp表
        int n = nums.length;
        int[] dp = new int[n];
        //初始化
        dp[0] = 1;
        int ret = 1;
        //填表
        for(int i = 1; i < n; i++){
            dp[i] = 1;
            for(int j = i - 1; j >= 0; j--){
                if(nums[i] > nums[j] && dp[j] + 1 > dp[i]){
                    dp[i] = dp[j] + 1;
                }
            }
            ret = Math.max(ret, dp[i]);
        }
        //返回
        return ret;
    }
    //摆动序列
    public static int wiggleMaxLength(int[] nums) {
        int n = nums.length;
        //创建dp表
        int[] f = new int[n];
        int[] g = new int[n];
        f[0] = g[0] = 1;
        int ret = 1;
        for(int i = 1; i < n; i++){
            f[i] = g[i] = 1;
            //f[i]:以i位置为结尾，且递增
            //g[i]:以i位置为结尾，且递减
            for(int j = i-1; j >= 0; j--){
                if(nums[i] > nums[j] && g[j] + 1 > f[i]){
                    f[i] = g[j] + 1;
                }else if(nums[i] < nums[j] && f[j] + 1 > g[i]) {
                    g[i] = f[j] + 1;
                }
            }
            ret = Math.max(ret, Math.max(f[i], g[i]));
        }
        return ret;
    }
    //最长递增子序列的个数
    public static int findNumberOfLIS(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        int[] len = new int[n];
        dp[0] = len[0] = 1;
        int max = 1;
        int ret = 1;
        for(int i = 1; i < n; i++){
            dp[i] = len[i] = 1;
            for(int j = i - 1; j >= 0; j--){
                if(nums[i] > nums[j]){
                    if(dp[i] == dp[j] + 1){
                        len[i] += len[j];
                    }else if(dp[i] < dp[j] + 1){
                        dp[i] = dp[j] + 1;
                        len[i] = len[j];
                    }
                }
            }
            if(max == dp[i]) ret += len[i];
            else if(max < dp[i]){
                max = dp[i];
                ret = len[i];
            }
        }
        return ret;
    }

    public static void main(String[] args) {
        int[] nums = {1,3,5,4,7};
        wiggleMaxLength(nums);
        findNumberOfLIS(nums);
    }
}